package leetCode.function;

import java.util.stream.Stream;

import com.alibaba.fastjson.JSON;

public class HeapSort {
	
	public static void main(String[] args) {
		int arr[] = new int[] {3,4,8,1,9,0,3,6,3,7,76,14,65};
		System.out.println(JSON.toJSONString(new HeapSort().heapSort(arr)));
	}
	
	public int[] heapSort(int []arr) {
		int heapSize = arr.length;
		if(arr==null ||heapSize<2) return arr;
		Stream.iterate(0, i->i+1).limit(heapSize).forEach(i->{
			heapInsert(arr, i);
		});
		heapSize--;
		while(heapSize>0) {
			swap(arr, 0, heapSize);
			heapify(arr, 0, heapSize);
			heapSize--;
		}
		return arr;
	}
	
	private void heapInsert(int []arr, int index) {
		while(arr[index]>arr[(index-1)/2]) {
			swap(arr, index,(index-1)/2);
			index=(index-1)>>1;
		}
	}
	
	private void heapify(int []arr, int index, int heapSize) {
		int left = index * 2 + 1; // 左孩子的下标
		while (left < heapSize) { // 下方还有孩子的时候
			// 两个孩子中，谁的值大，把下标给largest
			// 1）只有左孩子，left -> largest
			// 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
			// 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
			int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
			// 父和较大的孩子之间，谁的值大，把下标给largest
			if(arr[largest] < arr[index]) break;
			swap(arr, largest, index);
			index = largest;
			left = index * 2 + 1;
		}
	}
	
	private void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}
